package LeetCode._02算法基础.day03双指针;

import LeetCode._01算法入门.day10递归回溯.ListNode;
import org.junit.Test;
import utils.MyPrintUtil;
import 题组.Solution;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 13 - 9:31
 * @Description 给定一个已排序的链表的头 head，删除原始链表中所有重复数字的节点
 * 只留下不同的数字，返回已排序的链表
 * @Version 中等
 */
public class _82删除排序链表的重复元素 {
    static ListNode head;   // 1->1->2->3->3->4

    @Test
    public void solve(){
        ListNode res = deleteDuplicates(head);
        MyPrintUtil.printSingleLinkedList(res);//2->4
    }
    /*by me 双指针*/
    public ListNode deleteDuplicates(ListNode head) {
        ListNode newHead = head;
        int value;

        //让newHead指向不重复节点
        while(newHead != null && newHead.next != null && newHead.val == newHead.next.val){
            while(newHead != null && newHead.next != null && newHead.val == newHead.next.val){
                newHead = newHead.next;
            }
            newHead = newHead.next;
        }

        ListNode l = newHead, r = newHead;
        while(r != null){
            value = r.val;
            //过滤重复
            while(r != null && r.val == value){
                r = r.next;
            }
            // l只能指向不重复节点
            if(!(r!= null && r.next != null && r.val == r.next.val)){
                l.next = r;
                l = r;
            }

        }
        return newHead;
    }
    /*官方思路*/
    //1.一次遍历
    public ListNode deleteDuplicates1(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode dummy = new ListNode(0, head);

        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }

    static {
        head = new ListNode(1);
        ListNode l1 = new ListNode(1);
        head.next = l1;

        ListNode l2 = new ListNode(2);
        l1.next = l2;

        ListNode l3 = new ListNode(3);
        l2.next = l3;

        ListNode l4 = new ListNode(3);
        l3.next = l4;

        l4.next = new ListNode(4);
    }

}
